package JZ_Offer.dataStructure.tree;

import base.TreeNode;

import java.util.Arrays;
import java.util.List;

/**
 * 序列化二叉树
 * <p>
 * 请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。
 * <p>
 * 二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。
 * 序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#）
 * <p>
 * 二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
 * <p>
 * 例如，可以根据层序遍历的方案序列化:
 * 层序序列化(即用函数Serialize转化)如上的二叉树转为"{1,2,3,#,#,6,7}"，再能够调用反序列化(Deserialize)将"{1,2,3,#,#,6,7}"构造成如上的二叉树。
 */
public class JZ37_序列化二叉树 {

    /**
     * 1 根据二叉树和数组下标的对应关系
     * 序列化 -> 将二叉树转化为数组，然后将数组以某种形式存为字符串
     * 反序列化 -> 将字符串转为数组，然后将数组转换为二叉树
     */

    // 序列化
    static String Serialize(TreeNode root) {
        Object[] array = new Object[50];
        serRecursive(array, 1, root);
        StringBuilder builder = new StringBuilder();
        for (Object s : array) {
            if (s == null) {
                builder.append("#").append(",");
            } else {
                builder.append(s).append(",");
            }
        }
        return builder.toString();
    }

    // 反序列化
    static TreeNode Deserialize(String str) {
        List<String> list = Arrays.asList(str.split(","));
        String r0 = list.get(0);
        if ("#".equals(r0)) {
            return null;
        }

        TreeNode root = new TreeNode(Integer.parseInt(r0));
        desRecursive(list, 1, root);
        return root;
    }

    // 递归将二叉树对应到数组堆
    private static void serRecursive(Object[] array, Integer nodeIdx, TreeNode node) {
        if (node == null) {
            return;
        }
        array[nodeIdx - 1] = node.val;
        serRecursive(array, nodeIdx * 2, node.left);
        serRecursive(array, nodeIdx * 2 + 1, node.right);
    }

    // 递归将数组堆还原成二叉树
    private static void desRecursive(List<String> list, Integer nodeIdx, TreeNode node) {
        int l = nodeIdx * 2;
        int r = nodeIdx * 2 + 1;
        int size = list.size();

        if ((l - 1) < size && !"#".equals(list.get(l - 1))) {
            TreeNode lnode = new TreeNode(Integer.parseInt(list.get(l - 1)));
            node.left = lnode;
            desRecursive(list, l, lnode);
        }

        if ((r - 1) < size && !"#".equals(list.get(r - 1))) {
            TreeNode lnode = new TreeNode(Integer.parseInt(list.get(r - 1)));
            node.right = lnode;
            desRecursive(list, r, lnode);
        }
    }

    public static void main(String[] args) {
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(4);
        TreeNode f = new TreeNode(6);
        TreeNode g = new TreeNode(7);

        a.left = b;
        a.right = c;
        b.left = d;
        c.left = f;
        c.right = g;

        String s = Serialize(a);
        TreeNode root = Deserialize(s);
        System.out.println();
    }

}
